<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>一致性哈希算法详解</title>
    <link href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css" rel="stylesheet">
    <link href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css" rel="stylesheet">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
        }
        .serif-font {
            font-family: 'Noto Serif SC', serif;
        }
        .gradient-text {
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
            -webkit-background-clip: text;
            -webkit-text-fill-color: transparent;
            background-clip: text;
        }
        .hero-gradient {
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
        }
        .card-hover {
            transition: all 0.3s ease;
        }
        .card-hover:hover {
            transform: translateY(-4px);
            box-shadow: 0 20px 40px rgba(0,0,0,0.1);
        }
        .code-block {
            background: #1e1e1e;
            border-radius: 12px;
            overflow: hidden;
        }
        .code-header {
            background: #2d2d2d;
            padding: 12px 20px;
            display: flex;
            align-items: center;
            justify-content: space-between;
        }
        pre {
            margin: 0;
            padding: 20px;
            overflow-x: auto;
            color: #d4d4d4;
            font-size: 14px;
            line-height: 1.6;
        }
        .keyword { color: #569cd6; }
        .string { color: #ce9178; }
        .comment { color: #6a9955; }
        .number { color: #b5cea8; }
        .function { color: #dcdcaa; }
        .drop-cap {
            float: left;
            font-size: 4rem;
            line-height: 1;
            font-weight: 700;
            margin-right: 0.5rem;
            margin-top: -0.1rem;
            color: #667eea;
        }
        .mermaid {
            display: flex;
            justify-content: center;
            margin: 2rem 0;
        }
        .feature-icon {
            width: 60px;
            height: 60px;
            display: flex;
            align-items: center;
            justify-content: center;
            border-radius: 12px;
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
            color: white;
            font-size: 24px;
            margin-bottom: 1rem;
        }
    </style>
</head>
<body class="bg-gray-50">
    <!-- Hero Section -->
    <section class="hero-gradient text-white py-20 px-6">
        <div class="max-w-6xl mx-auto">
            <div class="text-center">
                <h1 class="text-5xl md:text-6xl font-bold mb-6 serif-font">一致性哈希算法</h1>
                <p class="text-xl md:text-2xl mb-8 opacity-90">分布式系统中的数据均衡艺术</p>
                <div class="flex justify-center space-x-6 text-sm">
                    <span class="flex items-center"><i class="fas fa-server mr-2"></i>分布式系统</span>
                    <span class="flex items-center"><i class="fas fa-balance-scale mr-2"></i>负载均衡</span>
                    <span class="flex items-center"><i class="fas fa-exchange-alt mr-2"></i>最小化迁移</span>
                </div>
            </div>
        </div>
    </section>

    <!-- Main Content -->
    <main class="max-w-6xl mx-auto px-6 py-12">
        <!-- Problem Description -->
        <section class="mb-16">
            <div class="bg-white rounded-2xl shadow-lg p-8 card-hover">
                <h2 class="text-3xl font-bold mb-6 flex items-center">
                    <i class="fas fa-question-circle text-purple-600 mr-3"></i>
                    问题描述
                </h2>
                <p class="text-lg leading-relaxed text-gray-700">
                    <span class="drop-cap serif-font">在</span>分布式系统中，如何将数据均匀分布到多台服务器上，并在服务器增减时尽量减少数据迁移？这是一个经典的分布式系统设计问题。一致性哈希算法通过将节点和数据映射到一个虚拟的环形空间，优雅地解决了这个挑战。
                </p>
            </div>
        </section>

        <!-- Core Concepts -->
        <section class="mb-16">
            <h2 class="text-3xl font-bold mb-8 text-center gradient-text">核心概念</h2>
            <div class="grid md:grid-cols-3 gap-6">
                <div class="bg-white rounded-xl shadow-md p-6 card-hover">
                    <div class="feature-icon">
                        <i class="fas fa-ring"></i>
                    </div>
                    <h3 class="text-xl font-bold mb-3">哈希环</h3>
                    <p class="text-gray-600">将整个哈希值空间组织成一个虚拟的圆环，数据和节点都映射到环上的点。</p>
                </div>
                <div class="bg-white rounded-xl shadow-md p-6 card-hover">
                    <div class="feature-icon">
                        <i class="fas fa-clone"></i>
                    </div>
                    <h3 class="text-xl font-bold mb-3">虚拟节点</h3>
                    <p class="text-gray-600">每个物理节点对应多个虚拟节点，提高数据分布的均匀性。</p>
                </div>
                <div class="bg-white rounded-xl shadow-md p-6 card-hover">
                    <div class="feature-icon">
                        <i class="fas fa-arrows-alt"></i>
                    </div>
                    <h3 class="text-xl font-bold mb-3">最小迁移</h3>
                    <p class="text-gray-600">节点增减时，只影响相邻节点的数据，大大减少数据迁移量。</p>
                </div>
            </div>
        </section>

        <!-- Algorithm Visualization -->
        <section class="mb-16">
            <div class="bg-white rounded-2xl shadow-lg p-8">
                <h2 class="text-3xl font-bold mb-6 flex items-center">
                    <i class="fas fa-project-diagram text-purple-600 mr-3"></i>
                    算法原理可视化
                </h2>
                <div class="mermaid">
                    graph LR
                        subgraph "哈希环"
                            A[节点A:0<br/>hash=100] 
                            B[节点A:1<br/>hash=300]
                            C[节点B:0<br/>hash=500]
                            D[节点B:1<br/>hash=700]
                            E[节点C:0<br/>hash=900]
                            F[节点C:1<br/>hash=1100]
                        end
                        
                        K1[键1<br/>hash=250] --> B
                        K2[键2<br/>hash=600] --> D
                        K3[键3<br/>hash=1000] --> F
                        
                        style A fill:#667eea,stroke:#333,stroke-width:2px,color:#fff
                        style B fill:#667eea,stroke:#333,stroke-width:2px,color:#fff
                        style C fill:#764ba2,stroke:#333,stroke-width:2px,color:#fff
                        style D fill:#764ba2,stroke:#333,stroke-width:2px,color:#fff
                        style E fill:#f093fb,stroke:#333,stroke-width:2px,color:#fff
                        style F fill:#f093fb,stroke:#333,stroke-width:2px,color:#fff
                        style K1 fill:#ffd93d,stroke:#333,stroke-width:2px
                        style K2 fill:#ffd93d,stroke:#333,stroke-width:2px
                        style K3 fill:#ffd93d,stroke:#333,stroke-width:2px
                </div>
                <p class="text-gray-600 mt-6 text-center">
                    <i class="fas fa-info-circle mr-2"></i>
                    数据键通过哈希函数映射到环上，顺时针找到第一个节点即为负责节点
                </p>
            </div>
        </section>

        <!-- Solution Approach -->
        <section class="mb-16">
            <div class="bg-gradient-to-r from-purple-50 to-pink-50 rounded-2xl p-8">
                <h2 class="text-3xl font-bold mb-6">解题思路</h2>
                <div class="space-y-4">
                    <div class="flex items-start">
                        <span class="flex-shrink-0 w-8 h-8 bg-purple-600 text-white rounded-full flex items-center justify-center font-bold mr-4">1</span>
                        <div>
                            <h4 class="font-bold mb-1">构建哈希环</h4>
                            <p class="text-gray-700">使用TreeMap存储虚拟节点，自动维护有序性</p>
                        </div>
                    </div>
                    <div class="flex items-start">
                        <span class="flex-shrink-0 w-8 h-8 bg-purple-600 text-white rounded-full flex items-center justify-center font-bold mr-4">2</span>
                        <div>
                            <h4 class="font-bold mb-1">虚拟节点映射</h4>
                            <p class="text-gray-700">每个物理节点创建多个虚拟节点，提高负载均衡性</p>
                        </div>
                    </div>
                    <div class="flex items-start">
                        <span class="flex-shrink-0 w-8 h-8 bg-purple-600 text-white rounded-full flex items-center justify-center font-bold mr-4">3</span>
                        <div>
                            <h4 class="font-bold mb-1">数据定位</h4>
                            <p class="text-gray-700">使用tailMap查找顺时针方向第一个节点</p>
                        </div>
                    </div>
                </div>
                <div class="mt-6 bg-white rounded-lg p-4">
                    <p class="text-sm text-gray-600">
                        <i class="fas fa-clock mr-2"></i>
                        <strong>时间复杂度：</strong>O(log n) 查找节点
                        <span class="mx-4">|</span>
                        <i class="fas fa-memory mr-2"></i>
                        <strong>空间复杂度：</strong>O(n) 存储虚拟节点
                    </p>
                </div>
            </div>
        </section>

        <!-- Code Implementation -->
        <section class="mb-16">
            <h2 class="text-3xl font-bold mb-6">完整实现代码</h2>
            <div class="code-block">
                <div class="code-header">
                    <div class="flex items-center">
                        <i class="fab fa-java text-orange-500 mr-2"></i>
                        <span class="text-gray-300">ConsistentHashing.java</span>
                    </div>
                    <button class="text-gray-400 hover:text-white transition-colors">
                        <i class="fas fa-copy"></i>
                    </button>
                </div>
                <pre><code><span class="keyword">import</span> java.util.SortedMap;
<span class="keyword">import</span> java.util.TreeMap;
<span class="keyword">import</span> java.util.Collection;
<span class="keyword">import</span> java.util.HashMap;
<span class="keyword">import</span> java.util.Map;

<span class="comment">/**
 * 一致性哈希算法实现
 * 用于分布式系统中数据的均匀分布和减少节点变化时的数据迁移
 */</span>
<span class="keyword">public class</span> <span class="function">ConsistentHashing</span> {
    <span class="comment">// 虚拟节点的复制因子，越大分布越均匀</span>
    <span class="keyword">private final int</span> numberOfReplicas;
    <span class="comment">// 存储虚拟节点的哈希值到实际节点的映射</span>
    <span class="keyword">private final</span> SortedMap&lt;Integer, String&gt; circle = <span class="keyword">new</span> TreeMap&lt;&gt;();
    <span class="comment">// 存储实际节点到其虚拟节点哈希值的映射</span>
    <span class="keyword">private final</span> Map&lt;String, Collection&lt;Integer&gt;&gt; nodeToHashes = <span class="keyword">new</span> HashMap&lt;&gt;();
    
    <span class="comment">/**
     * 构造函数
     * @param numberOfReplicas 每个节点的虚拟节点数量
     */</span>
    <span class="keyword">public</span> <span class="function">ConsistentHashing</span>(<span class="keyword">int</span> numberOfReplicas) {
        <span class="keyword">this</span>.numberOfReplicas = numberOfReplicas;
    }
    
    <span class="comment">/**
     * 添加节点到哈希环
     * @param node 节点名称
     */</span>
    <span class="keyword">public void</span> <span